// https://www.lintcode.com/problem/144/

class Solution {
public:
    /*
     * @param A: An integer array.
     * @return: nothing
     */

    void partion(vector<int> &A, int start_positive) {
        int low = 0;
        int high = A.size() - 1;
        int flag;
        if (start_positive) {
            flag = 1;
        } else {
            flag = -1;
        }
        while (low < high) {
            while (A[low] * flag > 0) {
                low++;
            }
            while (A[high] * flag < 0) {
                high--;
            }
            if (low <= high) {
                swap(A[low], A[high]);
                low++;
                high--;
            }
        }
    }
    void interleave(vector<int> &A, int has_same_length) {
        int l = 1;
        int r = A.size() - 1;
        if (has_same_length) {
            r--;
        }
        while (l < r) {
            swap(A[l], A[r]);
            // l++;
            // r--;
            l += 2;
            r -= 2;
        }
    }
    void rerange(vector<int> &A) {
        int pos = 0;
        int neg = 0;
        for (int num: A) {
            if (num > 0) {
                pos++;
            } else {
                neg++;
            }
        }
        partion(A, pos > neg);
        interleave(A, pos == neg);
    }
};